'''
https://leetcode.cn/problems/maximum-sum-circular-subarray/description/
'''

from typing import List

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        n = len(nums)
        a_max_sum, a_min_sum = nums[0], nums[0]     # 以a结尾，的最大累加和，和最小累加和
        max_sum, min_sum = a_max_sum, a_min_sum     # 整个区间上的最大累加和，和最小累加和
        for i in range(1, n):
            a_max_sum = max(nums[i] + a_max_sum, nums[i])
            max_sum = max(max_sum, a_max_sum)

            a_min_sum = min(nums[i] + a_min_sum, nums[i])
            min_sum = min(min_sum, a_min_sum)
        all_sum = sum(nums)
        # 答案： 1) 最大累加和
        #       2) 左边一部分+右边一部分 = 所有累加和-中间一部分，中间一部分应该是啥呢？就是最小累加和的那部分
        #   3）特例，如果都是负数，那么all_sum - min_sum就是0，防止这个特例
        return max_sum if all_sum == min_sum else max(max_sum, all_sum - min_sum)

